package chapter01;

public class IsMatch {
    //动态规划
    public static boolean isMatch(String s, String p) {
        int m=s.length();
        int n=p.length();
        int i,j;
        boolean[][] result=new boolean[m+1][n+1];
        result[0][0]=true;
        if(m<1){
            return n==0;
        }
//         for(i=1;i<=m;i++){
//             result[i][0]=false;
//         }
        for(j=1;j<=n;j++){
            if(p.charAt(j-1)=='*'){
                result[0][j]=result[0][j-2];
            }
//            else{
//                result[0][j]=false;
//            }
        }
        for (i=1;i<=m;i++){
            for(j=1;j<=n;j++){
                if(s.charAt(i-1)==p.charAt(j-1)||p.charAt(j-1)=='.'){
                    result[i][j]=result[i-1][j-1];
                }else{
                    if(p.charAt(j-1)=='*'){
                        if(p.charAt(j-2)==s.charAt(i-1)||p.charAt(j-2)=='.'){
                            result[i][j]=result[i][j-2]||result[i-1][j];
                        }else{
                            result[i][j]=result[i][j-2];
                        }
                    }
//                    else{
//                        result[i][j]=false;
//                    }
                }
            }
        }
        return result[m][n];
    }

    public static void main(String[] args) {
        System.out.println(isMatch("mississippi","mis*is*p*"));
    }
}
